"""
时间复杂度：O(n log n)
"""

def sift(li, low, high):
    """
    堆排序
    :param li:  列表
    :param low: 堆的根节点位置
    :param high:堆的最后一个元素位置
    :return:
    """
    i = low  # i最开始指向根节点
    j = 2 * i + 1  # j开始指向左边子节点

    tmp = li[low]  # 把堆顶存起来

    while j <= high:  # 只要j位置有效，就还在范围内

        if j + 1 <= high and li[j + 1] > li[j]:  # 如果有右节点，并且比左节点大
            j = j + 1

        if li[j] > tmp:  # 如果子节点有比堆顶大的，i移到该最大的子节点。继续往下层
            li[i] = li[j]
            i = j
            j = 2 * i + 1
        else:  # tmp更大，把tmp放在i的位置上
            li[i] = tmp  # 把tmp放到某一级领导位置上
            break

    else:
        li[i] = tmp  # 把tmp放在叶子节点上


def heap_sort(li):
    n = len(li)
    for i in range((n - 2) // 2, -1, -1):
        # i表示建堆的时候调整到部分的跟的下表
        sift(li, i, n - 1)
    # 建堆完成
    for i in range(n - 1, -1, -1):
        # i指向当前堆的最后一个元素
        li[0], li[i] = li[i], li[0]
        sift(li, 0, i - 1)  # i-1s最新的high


li = [i for i in range(100)]
import random

random.shuffle(li)
print(li)

heap_sort(li)

print(li)



